#include <vector>

// 时间复杂度为O(N*logN)
// 空间复杂度为O(1)
// 堆排序不稳定的

// 向下调整
void adjustDown(std::vector<int> &nums, int n, int parent)
{
    int maxchild = parent * 2 + 1;
    while (maxchild < n)
    {
        // 找到较大的那个孩子
        if (maxchild + 1 < n && nums[maxchild] < nums[maxchild + 1])
        {
            maxchild++;
        }

        if (nums[parent] < nums[maxchild])
        {
            std::swap(nums[parent], nums[maxchild]);

            // 迭代
            parent = maxchild;
            maxchild = parent * 2 + 1;
        }
        else
            break;
    }
}

void heapSort(std::vector<int> &nums)
{
    int n = nums.size();

    // 向下调整建堆 O(N)
    for (int i = (n - 1 - 1 / 2); i >= 0; i--)
    {
        adjustDown(nums, n, i);
    }

    // O(N*logN)
    int i = 1;
    while (i < n)
    {
        // 将最后一个数和第一个进行交换
        std::swap(nums[0], nums[n - i]);
        // 重新进行调整堆
        adjustDown(nums, n - i, 0);
        i++;
    }
}